#include <vector>
#include <algorithm>

using std::vector;
using std::sort;
using std::greater;

int maxPoint(vector<int>& uniq, vector<int>& cnt, int start, vector<int>& res) {
    printf("=-= maxPoint start: %d\n", start);
    if (start >= uniq.size()) {
        return 0;
    }
    if (res[start] != 0) {
        printf("=-= maxPoint start: %d return res[start]\n", start);
        return res[start];
    }
    if (start == uniq.size() - 1) {
        res[start] = uniq[start] * cnt[start];
        printf("=-= maxPoint start: %d only 1 result: %d\n", start, res[start]);
        return res[start];
    }
    int case1;
    int case2;
    int pointAtStart = uniq[start] * cnt[start];
    if (uniq[start] - uniq[start+1] == 1) {
        case1 = pointAtStart + maxPoint(uniq, cnt, start+2, res);
        printf("=-= maxPoint start: %d case1: %d\n", start, case1);
        case2 = maxPoint(uniq, cnt, start+1, res);
        printf("=-= maxPoint start: %d case2: %d\n", start, case2);
        if (case1 >= case2) {
            res[start] = case1;
        } else {
            res[start] = case2;
        }
    } else {
        res[start] = pointAtStart + maxPoint(uniq, cnt, start+1, res);
        printf("=-= maxPoint start: %d case3: %d\n", start, case2);
    }
    return res[start];
}

int deleteAndEarn(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    // make sure nums is sorted
    sort(nums.begin(), nums.end(), greater<int>());

    // uniq the items
    vector<int> numsUniq;
    vector<int> numsCount;
    int i = 1;
    int k = 1;
    numsUniq.push_back(nums[0]);
    numsCount.push_back(1);

    int nums_len = nums.size();
    for (; i < nums_len; i++) {
        if (nums[i] != nums[i-1]) {
            numsUniq.push_back(nums[i]);
            numsCount.push_back(1);
            k++;
        } else {
            numsCount[k-1]++;
        }
    }

    for (auto i : numsUniq) {
        printf("%d ", i);
    }
    printf("-- numsUniq\n");
    for (auto i : numsCount) {
        printf("%d ", i);
    }
    printf("-- numsCount\n");

    // to record the result for each start
    vector<int> result(numsUniq.size(), 0);
    return maxPoint(numsUniq, numsCount, 0, result);
}

int main() {
    vector<int> v{ 4, 2, 3, 3, 3, 2, 3, 4, 3 };
    int point = deleteAndEarn(v);
    printf("point: %d\n", point);
    
    v = { 1,3 };
    point = deleteAndEarn(v);
    printf("point: %d\n", point);
}

